home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 347_01 / tavlrebl.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-10-18  |  6.0 KB  |  184 lines
  1. /*:file:version:date: "%n    V.%v;  %f"
  2.  * "TAVLREBL.C    V.9;  20-Oct-91,13:38:42"
  3.  *
  4.  *  Module:  Rebalance
  5.  *  Purpose: Rebalance the TAVLtree "a", which is unbalanced by at most
  6.  *           one leaf.  This function may be called by either "tavl_insert"
  7.  *           or "tavl_delete"; Rebalance is considered to be private to the
  8.  *           TAVL routines, its prototype is in the header "tavlpriv.h",
  9.  *           whereas user routine prototypes are in "tavltree.h".
  10.  *           Assumes balance factors & threads are correct; Returns pointer
  11.  *           to root of balanced tree; threads & balance factors have been
  12.  *           corrected if necessary.  If the height of the subtree "a"
  13.  *           decreases by one, tavl_rebalance sets *deltaht to 1, otherwise
  14.  *           *deltaht is set to 0.  If "tavl_rebalance" is called by
  15.  *           "tavl_insert", *deltaht will always be set to 1 - just by the
  16.  *           nature of the algorithm.  So the function "tavl_insert" does
  17.  *           not need the information provided by *deltaht;  however,
  18.  *           "tavl_delete" does use this information.
  19.  *
  20.  *  Author:  Bert C. Hughes
  21.  *
  22.  * !!NOTE!!  This module must be linked into any program which uses
  23.  *           the TAVL library functions "tavl_insert" or "tavl_delete"!
  24.  *           This module is strictly for the use of those functions, and
  25.  *           is NOT intended to be a "user", or TAVL library, function.
  26.  *
  27.  *  Released to the PUBLIC DOMAIN
  28.  *                          Bert C. Hughes
  29.  *                          200 N.Saratoga
  30.  *                          St.Paul, MN 55104
  31.  *                          Compuserve 71211,577
  32.  */
  33.  
  34.    /* Debugging "assert"s are in the code to test integrity of the    */
  35.    /* tree. All assertions should be removed from production versions */
  36.    /* of the library by compiling the library with NDEBUG defined.    */
  37.    /* See the header "assert.h".*/
  38.  
  39. #include <stdlib.h>
  40. #include <assert.h>
  41. #include "tavltree.h"
  42. #include "tavlpriv.h"
  43.  
  44. TAVL_nodeptr rebalance_tavl(TAVL_nodeptr a, char *deltaht)
  45. {
  46.     TAVL_nodeptr b,c,sub_root;   /* sub_root will be the return value, */
  47.                                  /* and the root of the newly rebalanced*/
  48.                                  /* sub-tree */
  49.  
  50.                     /*  definition(tree-height(X)) : the maximum    */
  51.                     /*      path length from node X to a leaf node. */
  52.     *deltaht = 0;   /*  *deltaht is set to 1 if and only if         */
  53.                     /*      tree-height(rebalance()) < tree-height(a)*/
  54.  
  55.     if (Is_Head(a)          /* Never rebalance the head node! */
  56.         || abs(a->bf) <= 1) /* tree "a" is balanced - nothing more to do */
  57.         return(a);
  58.  
  59.     if (a->bf == LEFT+LEFT) {
  60.         b = a->Lptr;
  61.         if (b->bf != RIGHT) {   /* LL rotation */
  62.             if (RTHREAD(b)) {       /* b->Rptr is a thread to "a" */
  63.                 assert(b->Rptr == a);
  64.                 a->Lbit = THREAD;   /* change from link to thread */
  65.                 b->Rbit = LINK;     /* change thread to link */
  66.             }
  67.             else {
  68.                 a->Lptr = b->Rptr;
  69.                 b->Rptr = a;
  70.             }
  71.  
  72.             *deltaht = b->bf ? 1 : 0;
  73.             a->bf = - (b->bf += RIGHT);
  74.  
  75.             sub_root = b;
  76.         }
  77.         else {                  /* LR rotation */
  78.             *deltaht = 1;
  79.  
  80.             c = b->Rptr;
  81.             if (LTHREAD(c)) {
  82.                 assert(c->Lptr == b);
  83.                 c->Lbit = LINK;
  84.                 b->Rbit = THREAD;
  85.             }
  86.             else {
  87.                 b->Rptr = c->Lptr;
  88.                 c->Lptr = b;
  89.             }
  90.  
  91.             if (RTHREAD(c)) {
  92.                 assert(c->Rptr == a);
  93.                 c->Rbit = LINK;
  94.                 a->Lptr = c;
  95.                 a->Lbit = THREAD;
  96.             }
  97.             else {
  98.                 a->Lptr = c->Rptr;
  99.                 c->Rptr = a;
  100.             }
  101.  
  102.             switch (c->bf) {
  103.                 case LEFT:  b->bf = 0;
  104.                             a->bf = RIGHT;
  105.                             break;
  106.  
  107.                 case RIGHT: b->bf = LEFT;
  108.                             a->bf = 0;
  109.                             break;
  110.  
  111.                 case 0:     b->bf = 0;
  112.                             a->bf = 0;
  113.             }
  114.  
  115.             c->bf = 0;
  116.  
  117.             sub_root = c;
  118.         }
  119.     }
  120.     else if (a->bf == RIGHT+RIGHT) {
  121.         b = a->Rptr;
  122.         if (b->bf != LEFT) {    /* RR rotation */
  123.             if (LTHREAD(b)) {       /* b->Lptr is a thread to "a" */
  124.                 assert(b->Lptr == a);
  125.                 a->Rbit = THREAD;   /* change from link to thread */
  126.                 b->Lbit = LINK;     /* change thread to link */
  127.             }
  128.             else {
  129.                 a->Rptr = b->Lptr;
  130.                 b->Lptr = a;
  131.             }
  132.             *deltaht = b->bf ? 1 : 0;
  133.             a->bf = - (b->bf += LEFT);
  134.  
  135.             sub_root = b;
  136.         }
  137.         else {                  /* RL rotation */
  138.             *deltaht = 1;
  139.  
  140.             c = b->Lptr;
  141.             if (RTHREAD(c)) {
  142.                 assert(c->Rptr == b);
  143.                 c->Rbit = LINK;
  144.                 b->Lbit = THREAD;
  145.             }
  146.             else {
  147.                 b->Lptr = c->Rptr;
  148.                 c->Rptr = b;
  149.             }
  150.  
  151.             if (LTHREAD(c)) {
  152.                 assert(c->Lptr == a);
  153.                 c->Lbit = LINK;
  154.                 a->Rptr = c;
  155.                 a->Rbit = THREAD;
  156.             }
  157.             else {
  158.                 a->Rptr = c->Lptr;
  159.                 c->Lptr = a;
  160.             }
  161.  
  162.             switch (c->bf) {
  163.                 case RIGHT: b->bf = 0;
  164.                             a->bf = LEFT;
  165.                             break;
  166.  
  167.                 case LEFT:  b->bf = RIGHT;
  168.                             a->bf = 0;
  169.                             break;
  170.  
  171.                 case 0:     b->bf = 0;
  172.                             a->bf = 0;
  173.             }
  174.  
  175.             c->bf = 0;
  176.  
  177.             sub_root = c;
  178.         }
  179.     }
  180.  
  181.     return sub_root;
  182.  
  183. }/* end rebalance */
  184.